import java.util.Random;

//最小的K个数
//https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
public class Test {
    public static void main(String[] args) {
        //
    }
}

//老师写的（完全照搬？？？怎么也没通过？？？先看下一道吧）
class Solution {
    public int[] inventoryManagement(int[] nums, int k) {
        qsort(nums,0,nums.length-1,k);
        int[] ret = new int[k];
        for(int i=0;i<k;i++){
            ret[i] = nums[i];
        }
        return ret;
    }

    public void qsort(int[] nums,int l,int r,int k){
        if(l >= r)return;

        //1.随机选择一个基准元素 + 数组分三块
        int key = nums[new Random().nextInt(r-l+1)+l];
        int left = l-1,right = r+1,i=l;
        while(i<right){
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i]==key) i++;
            else swap(nums,--right,i);
        }

        //2.分类讨论
        int a = left - l + 1;
        int b = right - left - 1;
        if(a>b){
            qsort(nums,l,left,k);
        }else if(a+b>=k){
            return;
        }else{
            qsort(nums,right,r,k-a-b);
        }
    }
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}



//自己写的，有问题（暂时没有时间细看细改了，应该还是写问题，大体逻辑是理解的）
class Solution1 {
    public int[] inventoryManagement(int[] stock, int cnt) {
        //
        int l = 0;
        int r = stock.length - 1;
        qSort(stock,l,r,cnt);
        int[] res = new int[cnt];
        for(int i = 0; i < cnt; i++){
            res[i] = stock[i];
        }
        return res;
    }

    private void qSort(int[] stock, int l, int r, int cnt) {
        if (l >= r) {return;}

        int left = l - 1;
        int right = r + 1;
        int key = stock[new Random().nextInt(r-l+1)+l];
        int i = l;
        while (i < right) {
            if(stock[i] < key){
                swap(stock,++left,i++);
            }else if(stock[i] == key){
                i++;
            }else{
                swap(stock,i,--right);
            }
        }
        int a = left - r + 1;
        int b = (right-1) - (left+1) + 1;
        int c = r - right + 1;
        if(a>cnt){
            qSort(stock,l,left,cnt);
        }else if(a+b>=cnt){
            return;
        }else{
            qSort(stock,right,r,cnt-a-b);
        }

    }

    private void swap(int[] stock, int i, int j) {
        int temp = stock[i];
        stock[i] = stock[j];
        stock[j] = temp;
    }
}
